/*
 * @lc app=leetcode.cn id=496 lang=typescript
 *
 * [496] 下一个更大元素 I
 */

// @lc code=start

//  思路：单调栈
//  参考：https://labuladong.github.io/algo/2/18/43/

//  复杂度：O(n) O(n)

function nextGreaterElement(nums1: number[], nums2: number[]): number[] {
    const stack: number[] = []
    const map: Map<number, number> = new Map()
    const res: number[] = []
    // 先处理nums2 找出每个元素的结果存入哈希表
    for (let i = nums2.length - 1; i >= 0; i--) {
        while (stack.length && stack[stack.length - 1] <= nums2[i]) {
            // 矮个起开，反正也被挡着了。。。
            stack.pop()
        }
        map.set(nums2[i], stack.length ? stack[stack.length - 1] : -1)
        stack.push(nums2[i])
    }
    // 遍历nums1
    for (const num of nums1) {
        res.push(map.get(num)!)
    }

    return res
};
// @lc code=end

console.log(nextGreaterElement([4, 1, 2], [1, 3, 4, 2]))
console.log(nextGreaterElement([2, 4], [1, 2, 3, 4]))
